package com.java.base.exercise.algorithm.linestructure;

/**
 * @Author RenPu
 * @Date 2023/1/10 15:37
 * @Version 1.0
 * @Description: 自定义实现LinkedList数据结构
 **/
public class LinkedList<E> {


    //内部类
    private class Node{

       //当前元素
       private E e;
       //下一个元素
       private Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e,null);
        }

        public Node(){
            this(null,null);
        }
    }


    //链表长度记录
    private int size;

    //链表头结点
    private Node head;

    //无参构造方法，对链表长度和头结点进行设置默认值
    public LinkedList() {
        this.size=0;
        this.head=null;
    }

    //获取链表的元素个数
    public int getSize(){
        return this.size;
    }

    //获取链表是否为空值
    public boolean isEmpty(){
        return size==0;
    }

   //在链表中添加元素E（链表头添加元素E）
    public void addFirst(E e){

        /**优化--------前前前------的写法**/
//        Node node = new Node(e);
//        node.next=head; //需要插入的元素的next,指向head
//        head=node;      //将node节点，赋值给head,此时node就为链表的头结点


        /**优化--------后后后------的写法**/
        head=new Node(e,head);
        size++;         //维护好链表长度

    }


    //在链表中的指定索引值，进行元素的添加
    public void add(int index,E e){

        if(index<0 || index>size){
            throw new IllegalArgumentException("Add Failed. Illegal index ");
        }

        if(index==0){
            addFirst(e);
        }else {
            //假设需要插入的元素的前一个节点，从head开始匹配
            Node pre=head;
            //开始遍历，index-1个元素进行处理
            for (int i = 0; i <index-1 ; i++) {
                pre =pre.next;

                /**优化前-----------------**/
//                Node node = new Node(e);
//                node.next=pre.next;    需要插入的元素node，指向pre的下个节点
//                pre.next=node;         pre的下一个指针，指向需要插入的元素node ,此时完成将需要插入的元素node，连接在整个链表中


                /**优化后-----------------**/
                pre.next=new Node(e,pre.next);
                //维护链表长度
                size++;

            }
        }
    }


    //向链表尾部添加元素E
    public void addLast( E e){
        add(size,e);
    }



}
